//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 105 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 859 👎 0


package com.yun.leetcode.editor.cn;

import java.util.HashMap;

public class MinimumWindowSubstring {
    public static void main(String[] args) {
        Solution solution = new MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow("a", "aaa"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            // 注意用例，a,aa参数。
            // 并不是每个数出现一次，而是要满足需要出现的次数，所以还需要一个map
            // 双指针求最小覆盖子串
            HashMap<Character, Integer> map = new HashMap<>(6);
            HashMap<Character, Integer> need = new HashMap<>();
            int start = 0;
            int minLen = Integer.MAX_VALUE;
            int left = 0;
            int right = 0;
            // 先把right增加到包含全部t的子串。
            for (char c : t.toCharArray()) {
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            for (char c : t.toCharArray()) {
                map.put(c, 0);
            }
            char[] sChars = s.toCharArray();
            while (right < sChars.length) {

                if (map.containsKey(sChars[right])) {
                    map.put(sChars[right], map.get(sChars[right]) + 1);
                    while (map.entrySet().stream().allMatch(entry -> need.get(entry.getKey()) <= entry.getValue()) && left < sChars.length) {

                        if (right - left < minLen) {
                            start = left;
                            minLen = right - left;
                        }
                        if (map.containsKey(sChars[left])) {
                            // 两个问题，1.这里减去维护的字符个数，你记得减对了，别减右边界的，胡吃胡喝
                            map.put(sChars[left], map.get(sChars[left]) - 1);
                        }
                        left++;
                    }
                }
                right++;
            }

            return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen + 1); // 这里substring，记住api，包左不包右记得加一，参数是开始和结束的位置索引，
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}